package datastructure.book.tujiesuanfa.queueastack.exercise.first;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class Solution2 {

    /**
     * 使用O(n)时间复杂度
     * 输入：heights = [14,2,27,-5,28,13,39], limit = 3
     * 输出：[27,27,28,28,39]
     * 解释：
     *   滑动窗口的位置                最大值
     * ---------------               -----
     * [14 2 27] -5 28 13 39          27
     * 14 [2 27 -5] 28 13 39          27
     * 14 2 [27 -5 28] 13 39          28
     * 14 2 27 [-5 28 13] 39          28
     * 14 2 27 -5 [28 13 39]          39
     * 1 <= limit <= heights.length
     * -10000 <= heights[i] <= 10000
     */
    public int[] maxAltitude(int[] heights, int limit) {
        if (heights == null || heights.length == 0) {
            return new int[0];
        }
        int[] result = new int[heights.length - limit + 1];
        LinkedList<Integer> queue = new LinkedList<>();
        for (int i = 0; i < limit; i++) {
            int newValue = heights[i];
            while (!queue.isEmpty() && queue.getLast() < newValue) {
                queue.removeLast();
            }
            queue.add(newValue);
        }
        int index = 0;
        for (int i = 0; i < result.length; i++) {
            Integer peek = queue.getFirst();
            result[i] = peek;
            if (heights[index] == peek) {
                queue.poll();
            }
            index++;
            if (index + limit - 1 < heights.length){
                int newValue = heights[index + limit - 1];
                while (!queue.isEmpty() && queue.getLast() < newValue) {
                    queue.removeLast();
                }
                queue.add(newValue);
            }
        }
        return result;
    }
}
